package com.test.daily.leetcode.y2022.m06.day0611.v01;

import java.util.HashMap;
import java.util.Map;

/**
 * @descriptions: Solution
 * @author: Tom
 * @date: 2022/6/11 下午 01:20
 * @version: 1.0
 */
public class Solution {
    public static class Info {
        int[] zhang;
        int[] coin;
        public Info(){
 
        } 
    }
    public static Info getCoins(int[] arr){
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int ele : arr){
            map.put(ele, map.getOrDefault(ele, 0)+1);
        }
        int N = map.size();
        int i = 0;
        Info info = new Info();
        for(Map.Entry entry : map.entrySet()){
            info.coin[i] = (int)entry.getKey();
            info.zhang[i++] = (int)entry.getValue();
        }
        return info;
    }
    public static int coins(int [] arr, int aim){
        if(arr == null || arr.length == 0){
            return 0;
        }
        if(aim == 0){
            return 1;
        }
        Info info = getCoins(arr);
        int[] coins = info.coin;
        int[] zhang = info.zhang;
        return process(coins,zhang, 0, aim);
    }
    public static int process(int[] arr, int[] zhang, int index, int rest){
        if(index == arr.length){
            return rest == 0 ? 1 : 0;
        }
        int ans = 0;
        for(int i = 0; arr[i]* i <= rest && i < zhang[i];i++ ){
            ans += process(arr, zhang, index+1, rest -zhang[i]*i);
        }
        return ans;
    }

    public static int coin3(int[] arr, int aim){
        Info info = getCoins(arr);
        int[] coins = info.coin;
        int[] zhangs = info.zhang;
        int N = coins.length;
        int[][] dp = new int[N+1][aim+1];
        dp[N][0] = 1;
        for (int index = N-1; index >=0 ; index--) {
            for(int rest = 0; rest <= aim; rest++){
                int ans = 0;
                for(int zhang = 0; coins[index]*zhang <= rest&&zhang<zhangs[index]; zhang++){
                    ans += dp[index][rest-zhang*coins[index]];
                }
                dp[index][rest] = ans;
            }
        }
        return dp[0][aim];
    }

    public static int coin4(int[] arr, int aim){
        Info info = getCoins(arr);
        int[] coins = info.coin;
        int[] zhangs = info.zhang;
        int N = coins.length;
        int[][] dp = new int[N+1][aim+1];
        dp[N][0] = 1;
        for (int index = N-1; index >=0 ; index--) {
            for(int rest = 0; rest <= aim; rest++){
                dp[index][rest] = dp[index+1][rest];
                if(rest-coins[index] > 0){
                    dp[index][rest] += dp[index][rest-coins[index]];
                }
                if(rest-coins[index]*zhangs[index] > 0){
                    dp[index][rest] -= dp[index][rest-coins[index]*zhangs[index]];
                }
            }
//                int ans = 0;
//                for(int zhang = 0; arr[index]*zhang <= rest&&zhang<zhangs[index]; zhang++){
//                    ans += dp[index][rest-zhang*arr[index]];
//                }
//                dp[index][rest] = ans;
//            }
        }
        return dp[0][aim];
    }

}
